package fun.coding.jeffreys.judge;

public class LongestCommonSubsequence {

	public static void main(String[] args) {
		// Note this is for subsequence, not for sub string. 
		LongestCommonSubsequence ins = new LongestCommonSubsequence();
		String w1 = "abdabc";
		String w2 = "abcd";
		String w3 = "";
		String w4 = "bdab";
		
		String w5 = "baozi";
		String w6 = "azoi";
		
		assert ins.lcs(w1, w2) == 3;
		assert ins.lcs(w2, w3) == 0;
		assert ins.lcs(w4, w1) == 4;
		assert ins.lcs(w1, w1) == 6;
		assert ins.lcs(w5, w6) == 3;
		
		System.out.println(ins.lcs(w1, w2));
		System.out.println(ins.lcs("baozi training", "xbxaxo zxix"));

	}

	public int lcs(String w1, String w2) {
		if (w1 == null || w2 == null) return -1;
		
		int l1 = w1.length();
		int l2 = w2.length();
		
		if (l1 == 0 || l2 == 0) {
			return 0;
		}
		
		int[][] lookup = new int[l1+1][l2+1];
		
		for (int i = 0; i <= l1; i++) {
			lookup[i][0] = 0;
		}
		for (int i = 0; i <= l2; i++) {
			lookup[0][i] = 0;
		}
		
		/*
		 * dp[i][j] =  dp[i-1][j-1] +1  if (A[i] == B[j])
           or = max(dp[i][j-1], dp[i-1][j]);
			init value: dp[0][j] = 0, dp[i][0] = 0*/
		for (int i = 1; i <= l1; i++) {
			for (int j = 1; j <= l2; j++) {
				if (w1.charAt(i-1) == w2.charAt(j-1)) {
					lookup[i][j] = lookup[i-1][j-1] + 1;
				} else {
					lookup[i][j] = Math.max(lookup[i-1][j], lookup[i][j-1]);
				}
			}
		}
		
		return lookup[l1][l2];
		
	}
}
